package recursivecode.trymodel.left2right;

/**
 * 功能描述:背包最大重量问题
 * 2024/07/16
 *
 * @author ZhangYi
 */
public class BackPackMaxWeight {

	public static void main(String[] args) {
		int[] weight = {1, 10, 20, 4, 32};
		int[] value = {1, 10, 20, 4, 32};
		int bag = 6;
		System.out.println(backPack(weight, value, bag));

		System.out.println(backPack2(weight, value, bag));

		System.out.println(backPackFromCache(weight, value, bag));

		System.out.println(backPackFromCache2(weight, value, bag));
	}

	/**
	 * 背包问题来自cache2
	 *
	 * @param w   w
	 * @param v   v
	 * @param bag 包
	 * @return int
	 * @author ZhangYi
	 */
	private static int backPackFromCache2(int[] w, int[] v, int bag) {
		boolean returnCondition = (w == null || w.length == 0) || (v == null || v.length == 0);
		if (returnCondition) {
			return 0;
		}
		int N = w.length;
		int[][] dp = new int[N + 1][bag + 1];
		// 由于 int 初始化的时候 初始化为 0, 所以不需要额外的重置为 0
		for (int index = N - 1; index >= 0; index--) {
			for (int alreadyW = 0; alreadyW <= bag; alreadyW++) {
				int p1 = dp[index + 1][alreadyW];
				int p2 = -1;
				if (alreadyW + w[index] <= bag) {
					p2 = v[index] + dp[index + 1][alreadyW + w[index]];
				}

				dp[index][alreadyW] = Math.max(p1, p2);
			}
		}
		return dp[0][0];
	}

	/**
	 * 来自缓存背包
	 *
	 * @param w   w
	 * @param v   v
	 * @param bag 包
	 * @return int
	 * @author ZhangYi
	 */
	private static int backPackFromCache(int[] w, int[] v, int bag) {
		boolean returnCondition = (w == null || w.length == 0) || (v == null || v.length == 0);
		if (returnCondition) {
			return 0;
		}
		int N = w.length;
		int[][] dp = new int[N + 1][bag + 1];
		// index 来到最后一个元素, dp[index][]
		// 来到了背包的最后一个元素, 返回0 表示此方案是有效的
		for (int index = N - 1; index >= 0; index--) {
			for (int rest = 0; rest <= bag; rest++) {
				int p1 = dp[index + 1][rest];
				int p2 = -1;
				if (rest - w[index] >= 0) {
					p2 = v[index] + dp[index + 1][rest - w[index]];
				}
				dp[index][rest] = Math.max(p1, p2);
			}
		}

		return dp[0][bag];
	}



	/**
	 * 在背包的容量内,返回最大价值
	 *
	 * @param weight 重量
	 * @param value  值
	 * @param bag    包
	 * @return int
	 * @author ZhangYi
	 */
	private static int backPack2(int[] weight, int[] value, int bag) {
		boolean exitCondition =( (weight == null || weight.length == 0) || (value == null || value.length == 0))
				&& weight.length != value.length;
		if (exitCondition) {
			return 0;
		}
		return getMaxValueBackPack(weight,value,bag,0,0);
	}

	/**
	 * get max value back pack
	 *
	 * @param w        重量数组
	 * @param v        价值数组
	 * @param bag      背包容量
	 * @param index    索引下标
	 * @param alreadyW 当前已经使用的重量
	 * @return int
	 * @author ZhangYi
	 */
	private static int getMaxValueBackPack(int[] w, int[] v, int bag, int index, int alreadyW) {
		// 来到了背包的最后一个元素, 返回0 表示此方案是有效的
		if (index == w.length) {
			return 0;
		}
		// 如果当前元素大于背包容量, 则返回-1, 表示无效方案
		if (alreadyW + w[index] > bag) {
			return -1;
		}
		// 当前 索引 index 不装入背包, 直接进入下一个
		int p1 = getMaxValueBackPack(w, v, bag, index + 1, alreadyW);

		// 当前 索引 idnex 装入背包, 如果装入的方案是有效的,那么就 累加价值
		int p2 = -1;
		p2 = getMaxValueBackPack(w, v, bag, index + 1, alreadyW + w[index]);
		if (p2 != -1) {
			p2 += v[index];
		}
		return Math.max(p1, p2);
	}

	/**
	 * 背包: 背包在最大的容量内,返回最大的价值
	 *
	 * @param weight 重量
	 * @param value  价值
	 * @param bag    包
	 * @return int
	 * @author ZhangYi
	 */
	private static int backPack(int[] weight, int[] value, int bag) {
		boolean exitCondition = ((weight == null || weight.length == 0) || (value == null || value.length == 0))
				&& weight.length != value.length;
		if (exitCondition) {
			return 0;
		}
		return getMaxValueBackPack(weight,value,bag,0);
	}

	/**
	 * get max value back pack
	 *
	 * @param w         重量数组
	 * @param v         价值数组
	 * @param restSpace 背包剩余空间
	 * @param index     索引
	 * @return int
	 * @author ZhangYi
	 */
	private static int getMaxValueBackPack(int[] w, int[] v, int restSpace, int index) {
		// 来到了背包的最后一个元素, 返回0 表示此方案是有效的
		if (index == w.length) {
			return 0;
		}
		// 如果当前元素大于剩余空间, 则返回-1, 表示无效方案
		if (w[index] > restSpace) {
			return -1;
		}
		// 当前 索引 index 不装入背包, 直接进入下一个
		int p1 = getMaxValueBackPack(w, v, restSpace, index + 1);
		int p2 = -1;
		// 当前 索引 idnex 装入背包, 如果装入的方案是有效的,那么就 累加价值
		int p2Next = getMaxValueBackPack(w, v, restSpace - w[index], index + 1);
		if (p2Next != -1) {
			p2 += v[index] + p2Next;
		}
		return Math.max(p1, p2);
	}
}